import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Solution2 {

//    用来解决与链表节点不是很一致的部分
    static class Node {
         int val;
         Node next;
         Node random;
    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
/*  12：  复制带随机指针的链表
* 构造这个链表的 深拷贝。运用哈希
* my:先将链表搭建起来，然后利用map来搭建random*/
    public Node copyRandomList(Node head) {
        if (head==null)return null;
        Node cur=head;//指向head后面
        Map<Node,Node> map=new HashMap<>();
        while(cur != null) {
            //存放的是旧节点对应的新节点
            map.put(cur,new Node(cur.val));
            cur = cur.next;
        }
        cur=head;
        while(cur != null) {
            //取出map中的值,也就是新的节点,进行拷贝连接
            map.get(cur).next = map.get(cur.next);
            map.get(cur).random = map.get(cur.random);
            cur = cur.next;
        }
        //返回老结构对应的头,就是新结构对应的头节点
        return map.get(head);

    }

}
